package com.testProject.test.Sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        heapSort(arr);
    }

    public static void heapSort(int[] arr){
        for(int i=2*arr.length/2-1;i>=0;i--){
            swim(arr,i);
        }
        int[] res=new int[arr.length];
        for(int j=arr.length-1;j>=0;j--){
            int tmp=arr[0];
            arr[0]=arr[j];
            arr[j]=tmp;
            res[j]=tmp;
        }
        System.out.println(Arrays.toString(res));
    }

    //上浮，下沉 ,arr删除不方便，所以针对length范围内
    public static void swim(int[] arr,int k){
        while(k>0){
            if(arr[k]>arr[k/2]){
                int tmp=arr[k];
                arr[k]=arr[k/2];
                arr[k/2]=tmp;
            }
            k/=2;
        }
    }

    public static void sink(int[] arr,int k,int length){
        while(k<=length){
            //有右
            int max=Integer.MIN_VALUE;
            if(2*k+1<=length){
                max=arr[2*k]>arr[2*k+1]?2*k:2*k+1;
            }else{
                max=2*k;
            }
            if(arr[max]>arr[k]){
                int tmp=arr[max];
                arr[max]=arr[k];
                arr[k]=tmp;
            }
            k=max;
        }
    }
}
